package com.ming.learn.from.carl.doublepointer;

/*
题目：151.翻转字符串里的单词
 */
public class Of20201229LeetCode151 {
    /*
    给定一个字符串，逐个翻转字符串中的每个单词。
    示例 1：
    输入: "the sky is blue"
    输出: "blue is sky the"
    示例 2：
    输入: "  hello world!  "
    输出: "world! hello"
    解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
    示例 3：
    输入: "a good   example"
    输出: "example good a"
    解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
     */
    public static void main(String[] args) {
        System.out.println(reverseWords("  hello world!  "));
    }

    private static String removeExtraSpaces(String s) {
        char[] chars = s.toCharArray();
        int fastIndex = 0, slowIndex = 0;
        while (s.length() > 0 && fastIndex < s.length() && chars[fastIndex] == ' ') {
            fastIndex++;
        }
        for (; fastIndex < s.length(); fastIndex++) {
            if (fastIndex > 1 && chars[fastIndex - 1] == chars[fastIndex] && chars[fastIndex] == ' ') {
                continue;
            }
            chars[slowIndex++] = chars[fastIndex];
        }
        if (slowIndex > 1 && chars[slowIndex - 1] == ' ') {
            return new String(chars).substring(0, slowIndex - 1);
        }
        return new String(chars).substring(0, slowIndex);
    }

    private static String reverse(String s, int start, int end) {
        char[] chars = s.toCharArray();
        for (; start < end; start++, end--) {
            chars[start] ^= chars[end];
            chars[end] ^= chars[start];
            chars[start] ^= chars[end];
        }
        return new String(chars);
    }

    private static String reverseWords(String s) {
        s = removeExtraSpaces(s);
        s = reverse(s, 0, s.length() - 1);
        int start = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ' ') {
                s = reverse(s, start, i - 1);
                start = i + 1;
            }
        }
        s = reverse(s, start, s.length() - 1);
        return s;
    }

}
